package com.zlk.algorithm.dataStructure.linkList03;

import org.junit.Test;

/**
 * @program: algorithm
 * @ClassName Code12_IntersectionOfTwoLinkedLists  返回两个无环链表相交的第一个节点
 * @description:https://leetcode.cn/problems/intersection-of-two-linked-lists/
 * @author: slfang
 * @create: 2024-12-13 17:23
 * @Version 1.0
 **/
public class Code12_IntersectionOfTwoLinkedLists {

    public class ListNode {
      int val;
      ListNode next;
      ListNode(int x) {
          val = x;
          next = null;
      }
    }


    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) {
            return null;              //         |
        }
        ListNode cur1 = headA;
        ListNode cur2 = headB;
        int n1 = 0;
        int n2 = 0;
        while (cur1.next!=null){
            n1++;
            cur1 = cur1.next;
        }
        while (cur2.next!=null){
            n2++;
            cur2 = cur2.next;
        }
        if(cur1!=cur2){
            return null;
        }
//        cur1 = n1>=n2?headA:headB;
//        cur2 = n2<n1?headB:headA;
//        int diff =Math.abs(n1-n2);
        if (n1-n2 >= 0) {
            cur1 = headA;
            cur2 = headB;
        } else {
            cur1 = headB;
            cur2 = headA;
        }
        int n =Math.abs(n1-n2);
        n = Math.abs(n);
        while (n!=0){
            cur1=cur1.next;
            n--;
        }
        while (cur1!=cur2){
            cur1 = cur1.next;
            cur2 = cur2.next;
        }
        return cur1;
    }

    public ListNode getIntersectionNode2(ListNode headA, ListNode headB) {
        if(headA==null||headB==null){
            return null;
        }
        ListNode cur1 = headA;
        ListNode cur2 = headB;
        int n = 0;
        while (cur1.next!=null){
            cur1 = cur1.next;
            n++;
        }
        while (cur2.next!=null){
            cur2 = cur2.next;
            n--;
        }
        if(cur1!=cur2){
            return null;
        }
        if(n>=0){
            cur1 = headA;
            cur2 = headB;
        }else{
            cur2 = headA;
            cur1 = headB;
        }

        n = Math.abs(n);
        while (n!=0){
            cur1=cur1.next;
            n--;
        }
        while (cur1!=cur2){
            cur1 = cur1.next;
            cur2 = cur2.next;
        }
        return cur1;
    }
}
